#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define str string
#define all(x) (x).begin(),(x).end()
#define ms(a,t) memset(a,t,sizeof(a))
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define db double
const int maxn = 1e5+10;
const int mod = 998244353;
const ll INF = 0x3f3f3f3f;
const db eps = 1e-7;
int n,k;
struct Seg{
	int cnt[maxn<<2],mn[maxn<<2],tg[maxn<<2];
	void push_up(int p) {
		mn[p] = min(mn[p<<1],mn[p<<1|1]);
		cnt[p] = (mn[p] == mn[p<<1]) * cnt[p<<1] + (mn[p] == mn[p<<1|1]) * cnt[p<<1|1];
		mn[p] += tg[p];
	}
	void build(int p,int L = 1,int R = n) {
		if(L == R) {
			cnt[p] = 1;
			mn[p] = 0;
			tg[p] = 0;
			return;
		}
		tg[p] = 0;
		int mid = (L + R) >> 1;
		build(p<<1,L,mid); build(p<<1|1,mid+1,R);
		push_up(p);
	}
	void add(int p,int l,int r,int v,int L = 1,int R = n) {
		if(l <= L && R <= r) {
			tg[p] += v; mn[p] += v;
			return ;
		}
		int mid = (L + R) >> 1;
		if(l <= mid) add(p<<1,l,r,v,L,mid);
		if(r > mid) add(p<<1|1,l,r,v,mid+1,R);
		push_up(p);
	} 
	int query() {
		if(mn[1] == 0) return cnt[1];
		return 0;
	}
}t[16];
int pre[maxn][5];
int a[maxn];
bool c[maxn];
void Solve() {
	cin >> n >> k;
	for(int i = 0; i < (1<<k); i++) c[i] = __builtin_popcount(i)&1;
	for(int i = 1; i <= n; i++) for(int j = 0; j <= k; j++) pre[i][j] = 0;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for(int j = 0; j < (1<<k); j++) {
		t[j].build(1);
	}
	ll ret = 0;
	for(int i = 1; i <= n; i++) {
		int v = a[i];
		for(int j = 0; j < (1<<k); j++) {
			for(int x = 0; x < k; x++) if((j>>x)&1) {
				if(pre[v][x] == pre[v][x+1]) continue;
				t[j].add(1,pre[v][x+1]+1,pre[v][x],-1);
			}
		}
		for(int x = k; x >= 1; x--) {
			pre[v][x] = pre[v][x-1];
		}
		pre[v][0] = i;
		for(int j = 0; j < (1<<k); j++) {
			for(int x = 0; x < k; x++) if((j>>x)&1) {
				if(pre[v][x] == pre[v][x+1]) continue;
				t[j].add(1,pre[v][x+1]+1,pre[v][x],1);
			}
		}
		int tmp = 0;
		for(int j = 0; j < (1<<k); j++) {
			tmp += (c[j] ? -t[j].query() : t[j].query());
		}
		ret += tmp;
	}
	cout<<ret<<'\n';
	return ;
}
int main() {
	freopen("reporter.in","r",stdin);
	freopen("reporter.out","w",stdout);
//	cerr<<sizeof(t)/1024.0/1024<<'\n';
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T = 1;
//	cin >> T;
	while(T--) {
		Solve();
	}
	return 0;
}
